/*
 * ApostolicoCrochemore.cpp
 *
 *  Created on: 23-08-2013
 *      Author: Krzychu
 */

#include "ApostolicoCrochemore.h"

#include "Config.h"

#define MAX(a, b) (a > b) ? a : b

ApostolicoCrochemore::ApostolicoCrochemore()
{

}

ApostolicoCrochemore::~ApostolicoCrochemore()
{

}

std::string ApostolicoCrochemore::getName()
{
	return "Apolostico Crochemore";
}

searchResult ApostolicoCrochemore::execute(std::string text, std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textSize = text.size();
	int patternSize = pattern.size();

	int i, j, k, ell;

	/* Preprocessing */
	int* kmpNext = preKmp(pattern);

	for (ell = 1; pattern[ell - 1] == pattern[ell]; ell++);
	if (ell == patternSize)
	{
		ell = 0;
	}

	/* Searching */
	i = ell;
	j = k = 0;
	while (j <= textSize - patternSize)
	{
		result.iterationsTaken++;
		while (i < patternSize && pattern[i] == text[i + j])
		{
			++i;
		}
		if (i >= patternSize)
		{
			while (k < ell && pattern[k] == text[j + k])
			{
				++k;
			}
			if (k >= ell)
			{
				result.positionsFound.push_back(j);
				if (Config::getInstance()->getFindOneOccurence())
				{
					return result;
				}
			}
		}
		j += (i - kmpNext[i]);
		if (i == ell)
		{
			k = MAX(0, k - 1);
		}
		else if (kmpNext[i] <= ell)
		{
			k = MAX(0, kmpNext[i]);
			i = ell;
		}
		else
		{
			k = ell;
			i = kmpNext[i];
		}
	}

	return result;
}

